package DataStructureAndAlgorithm.Acwing.DP.最长子序列DP;

import java.util.Scanner;
//899. 编辑距离
class dp_899{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        //最长的字符串长度不超过10
        int N = 11;
        int n = in.nextInt();
        int m = in.nextInt();
        int[][] dp = new int[N][N];
        String[] origin = new String[n + 1];
        String query ;
        int step;
        int cnt;
        int[] res = new int[m + 1];
        //读入带查询的字符串
        for (int i = 1; i <= n; i++){
            origin[i] = in.next();
        }
        for (int l = 1; l<= m; l++){
            query = in.next();
            step = in.nextInt();
            cnt = 0;
            for (int i = 1; i <= n; i++){
                //下面的动规求解最短编辑距离的过程
                //此处初始化的dp[t][0]和dp[0][t]位置不能调换，初始化要按照dp的状态定义来初始化
                for (int t = 0; t <= origin[i].length(); t++) dp[t][0] = t;//初始化修改的操作数
                for (int t = 0; t <= query.length(); t++) dp[0][t] = t;//初始化增加的操作数
                for (int j = 1; j <= origin[i].length(); j++){
                    for (int k = 1; k <= query.length(); k++){
                        //[i-1][j]:表示a中的前i-1个字母和b中的前j个字母相同，即删除操作
                        //[i][j-1]:表示a中前i个字母和b中前j-1个字母相同，即增加操作
                        dp[j][k] = Math.min(dp[j - 1][k],dp[j][k - 1]) + 1;
                        //最后两个字符串在i和j的位置是否相同，如果相同，则不加1，否则，加1
                        if (origin[i].charAt(j - 1) == query.charAt(k - 1)){
                            dp[j][k] = Math.min(dp[j][k],dp[j - 1][k - 1]);
                        }else{
                            dp[j][k] = Math.min(dp[j][k],dp[j - 1][k - 1] + 1);
                        }
                    }
                }
                if (dp[origin[i].length()][query.length()] <= step){
                    cnt++;
                }
            }
            res[l] = cnt;
        }
        for (int i = 1; i <= m; i++){
            System.out.println(res[i]);
        }
    }
}
/*

给定 n
个长度不超过 10 的字符串以及 m

次询问，每次询问给出一个字符串和一个操作次数上限。

对于每次询问，请你求出给定的 n

个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。

每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式

第一行包含两个整数 n
和 m

。

接下来 n

行，每行包含一个字符串，表示给定的字符串。

再接下来 m

行，每行包含一个字符串和一个整数，表示一次询问。

字符串中只包含小写字母，且长度均不超过 10

。
输出格式

输出共 m

行，每行输出一个整数作为结果，表示一次询问中满足条件的字符串个数。
数据范围

1≤n,m≤1000

,
输入样例：

3 2
abc
acd
bcd
ab 1
acbd 2

输出样例：

1
3

 */